#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

// 1 结构体实现
#define TRUE 1  // 定义符号常量“真”
#define FALSE 0 // 定义符号常量“假”
#define MAXCHROMLENGTH 200
#define STEP 25
#define MINISTEP 13
#define MAXTRY 3
#define SIZE 8
typedef int STATUS;
int Maze[SIZE][SIZE] = {{0, 1, 0, 1, 0, 1, 0, 0},
                        {2, 1, 0, 1, 0, 1, 0, 0},
                        {0, 1, 0, 1, 1, 1, 1, 1},
                        {1, 1, 1, 1, 1, 1, 1, 0},
                        {1, 0, 0, 0, 1, 1, 0, 1},
                        {1, 0, 1, 0, 1, 1, 1, 1},
                        {1, 0, 1, 0, 1, 0, 1, 2},
                        {1, 1, 1, 0, 1, 0, 1, 0}};

typedef struct NODE // 节点类型
{
    int x, y;       // 横纵坐标
    float evaluate; // 未来开销
    double step;    // 历史开销
} NODE;

typedef struct NEIGHBORNODE // 路径类型
{
    NODE node;                 // 节点
    struct NEIGHBORNODE *next; // 相近节点
} NEIGHBORNODE, *NEIGHBOR;     // 相邻节点类型

typedef struct NEIGHBORNODE *PATH; // 路径类型

typedef struct Paths // 路径集合类型
{
    PATH path;          // 一条路径
    struct Paths *next; // 下一条路径
} Paths, *PATHS;        // 路径集合类型【*PATHS为指向PATH的指针】

typedef struct Paths *STACK; // 定义堆栈类型，实际上也是节点链表【相邻节点链表】

typedef struct INDIVIDUAL // 染色体结构类型
{
    int chrom[MAXCHROMLENGTH]; // 染色体二进制表达形式
    int chromlength;           // 染色体的实际长度
    double fitness;            // 染色体的适应度函数值
} INDIVIDUAL;                  // 染色体的个体类型

// 2.1 通用赋值函数
void Set(NODE *node1, NODE *node2)
{
    node1->x = node2->x;
    node1->y = node2->y;
    node1->evaluate = node2->evaluate;
    node1->step = node2->step;
}

// 2.2 通用判断函数
STATUS equal(NODE *node1, NODE *node2)
{
    if (node1->x == node2->x && node1->y == node2->y)
        return TRUE;
    else
        return FALSE;
}

// 2.3 显示迷宫节点
void PriNode(NODE node)
{
    printf("(%d,%d)", node.x, node.y);
}

// 2.4 显示路径信息
void PriPath(PATH path) // 显示路径
{
    while (path != NULL)
    {
        if (path->next != NULL)
        {
            PriNode(path->node);
            printf("->");
        }
        else
        {
            PriNode(path->node);
        }
        path = path->next;
    }
    printf("\n");
}

// 2.5 显示迷宫图
void PriMaze(PATH path, NODE start, NODE end)
{
    int temp[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            temp[i][j] = Maze[i][j];
        }
    }
    while (path != NULL)
    {
        temp[path->node.x][path->node.y] = 3;
        path = path->next;
    }
    temp[start.x][start.y] = 2;
    temp[end.x][end.y] = 2;
    printf("=========================\n");
    printf("图例说明: @:路径 ■:障碍 #:起终点 -:可行域\n");
    for (int i = 0; i < SIZE; i++)
    {
        for (int j = 0; j < SIZE; j++)
        {
            if (temp[i][j] == 3)
                printf(" @ ");
            else if (temp[i][j] == 0)
                printf(" ■ ");
            else if (temp[i][j] == 2)
                printf(" # ");
            else if (temp[i][j] == 1)
                printf(" - ");
        }
        printf("\n");
    }
}

// 2.6 通用延迟函数
void Delay()
{
    // printf("[INFO]休眠等待\n");
    // Sleep(10);                     //Win平台上单位是毫秒
    // printf("[INFO]休眠结束\n");
}

// 3.1 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br, NODE node) // Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b, pb;                                    // 相邻节点
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); // 动态开辟一个相邻节点
    Set(&(b->node), &node);                            // 【下面两行是类型为str时的情况，其他类比】
    b->next = NULL;
    if (br == NULL) // 没有相邻节点的情况
    {
        br = b; // node就是第一个邻居
    }
    else // 有相邻节点的情况
    {
        pb = br; // node就是最后一个相邻节点【值在b中，头插入】
        while (pb->next)
            pb = pb->next;
        pb->next = b;
    }
    return br; // 返回相邻节点【指针】
}

// 3.2 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br) // 回收相邻节点空间
{
    NEIGHBOR br1 = br; // 临时相邻变量
    while (br)         // 【遍历相邻节点】
    {
        br1 = br;
        br = br->next; // 【挨个变量赋给临时指针】
        free(br1);     // 回收单元
        return br;
    }
    return br; // 返回NULL
}

// 3.3 复制子节点集
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents) // 节点集复制
{
    NEIGHBOR copynode = NULL, lastnode = NULL, head = NULL; // 没有子节点
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(&copynode->node, &adjacents->node);
        copynode->next = NULL;
        if (head == NULL)
        {
            head = copynode; // 第1个节点
        }
        else
        {
            lastnode->next = copynode; // 非第1个节点：建立链接，复制子节点集
        }
        lastnode = copynode;
        adjacents = adjacents->next; // 下一个子节点
    }
    return head; // 返回头节点指针
}

// 3.4 复制路径和路径集合
PATH CopyPath(PATH path) // 复制一条路径，返回新路径
{
    PATH tempath;
    tempath = (PATH)CopyNeighbors((NEIGHBOR)path); // 路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths) // 复制路径集合
{
    PATHS copynode = NULL, lastnode = NULL, head = NULL;
    while (paths) // 路径集合不为空
    {
        copynode = (PATHS)malloc(sizeof(Paths)); // 路径节点
        copynode->path = CopyPath(paths->path);  // 复制一条路径
        copynode->next = NULL;                   // 复制路径初始化
        if (head == NULL)                        // 第1条路径
        {
            head = copynode;
        }
        else // 非第1条路径
        {
            lastnode->next = copynode;
        }
        lastnode = copynode; // 加入路径集合
        paths = paths->next;
    }
    return head;
}

// 3.5 节点加入路径
PATH Add_A_Node_To_Path(NODE *node, PATH path) // 在路径中加入一个节点形成新的路径
{
    PATH p;
    p = (NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    Set(&p->node, node);
    if (path == NULL) // 第1个节点
    {
        p->next = NULL;
    }
    else // 非第1个节点
    {
        p->next = path; // 加入到路径头部
    }
    path = p;    // 路径倒序加入
    return path; // 返回路径头部
}

// 3.6 路径加入路径集合
PATHS Add_A_Path_To_Paths(PATH path, PATHS paths) // 路径加入到路径集合中
{
    PATH copypath;
    PATHS ps = NULL, p;
    if (path == NULL)
        return paths;                  // 没有路径
    copypath = CopyPath(path);         // 复制路径
    ps = (PATHS)malloc(sizeof(Paths)); // 开辟路径集合节点
    ps->path = copypath;               // 复制的路径置入
    ps->next = NULL;
    if (paths == NULL) // 路径集合为空
    {
        paths = ps;
    }
    else // 路径集合为非空，新路径节点放置最后
    {
        p = paths;
        while (p->next)
            p = p->next;
        p->next = ps;
    }
    return paths;
}

// 3.7 路径进栈和所有节点进栈
5 // 一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    PATHS st;
    tempath = CopyPath(path);          // 复制节点
    st = (PATHS)malloc(sizeof(Paths)); // 路径节点
    st->path = tempath;                // 置路径于栈中
    if (stack == NULL)                 // 第1条路径
    {
        st->next = NULL;
    }
    else // 非第1条路径，已有路径
    {
        st->next = stack;
    }
    stack = st;
    return stack;
}

PATHS PushPaths(PATHS stack, PATHS paths) // 所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS p, head;
    head = CopyPaths(paths); // 复制路径集合
    p = head;
    if (p != NULL) // 逐一加入栈中
    {
        while (p->next)
            p = p->next;
        p->next = stack;
        stack = head;
    }
    return stack;
}

// 3.8 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack) // 回收栈空间
{
    stack = (STACK)ClearNeighbors((NEIGHBOR)stack); // 清除所有节点，得到空指针
    return stack;                                   // 返回空指针
}
PATH ClearPath(PATH path) // 回收路径空间
{
    path = (PATH)ClearNeighbors((NEIGHBOR)path); // 路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths) // 回收路径集合空间
{
    PATHS paths1 = paths;
    while (paths) // 所有路径
    {
        paths1 = paths;
        ClearPath(paths1->path); // 回收一条路径空间
        paths = paths->next;     // 下一条路径
        free(paths1);
    }
    return paths;
}

// 3.9 出栈与节点
PATHS Pop_A_Node(STACK stack, NODE *node, PATH *path) // 出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    PATHS p = stack;
    PATH tempath;
    if (p != NULL)
    {
        tempath = p->path; // 一条路径
        Set(node, &(tempath->node));
        *path = CopyPath(tempath); // 获取路径
        stack = p->next;           // 栈顶变化
        free(p);                   // 删除路径
    }
    return stack; // 返回栈顶
}

// 3.10 启发式出栈
STACK Pop_A_Node_Heuristic_by_Mini(STACK stack, NODE *node, PATH *path)
{
    STACK p = stack, p1 = NULL, p2, p3;
    PATH tempath;
    double ev = 1e100;
    if (p == NULL)
        return stack;
    *path = NULL;
    while (p != NULL)
    {
        tempath = p->path;
        if (tempath->node.evaluate + tempath->node.step < ev)
        {
            ev = tempath->node.evaluate + tempath->node.step;
            p2 = p1;
            p3 = p;
        }
        p1 = p;
        p = p->next;
    }
    tempath = p3->path;
    Set(node, &(tempath->node));
    *path = CopyPath(tempath);
    if (p3 == stack)
    {
        stack = p3->next;
    }
    else
    {
        p2->next = p3->next;
    }
    free(p3);
    return stack;
}

// 3.11 路径倒叙
void RevPath(PATH path) // 路径倒序，按树根倒目标节点的顺序
{
    int num = 0, i;
    NODE *nodes;
    PATH p = path;
    while (p) // 统计路径节点的个数
    {
        p = p->next;
        num++;
    }
    nodes = (NODE *)malloc(num * sizeof(NODE)); // 开辟一维数组
    for (i = 0, p = path; p; p = p->next, i++)  // 读取路径节点置于数组中
    {
        Set(&nodes[i], &(p->node));
    }
    for (i = num - 1, p = path; p; p = p->next, i--) // 数组数据倒序置于路径中
    {
        Set(&(p->node), &nodes[i]);
    }
    free(nodes); // 回收数组空间
}

// 4.1 判断节点是否在路径中
STATUS IsInPath(NODE node, PATH path) // 判断节点是否在路径中并返回真或假
{
    PATH p = path;
    STATUS flag = FALSE; // 节点是否在路径中的标识
    while (p)
    {
        if (equal(&node, &p->node) != 0) // node在路径中
        {
            flag = TRUE;
            break;
        }
        else // node不在路径中
        {
            p = p->next;
        }
    }
    return flag; // 返回真/假
}

// 4.2 删除在路径中的节点
NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path) // 从节点集合adjacents中删除节点在路径path中的节点
{
    NEIGHBOR n1 = adjacents, n2 = NULL;
    STATUS flag = FALSE;
    while (n1) // 遍历节点集合中的每个节点
    {
        flag = IsInPath(n1->node, path); // 节点是否在路径中
        if (flag == TRUE)
        {
            if (n1 == adjacents) // 待删除节点位于第一个
            {
                adjacents = n1->next; // 下一个节点
                free(n1);             // 删除当前节点
                n1 = adjacents;       // 其他节点
            }
            else // 待删除节点不在第一个
            {
                n2->next = n1->next; // NULL
                free(n1);            // 删除当前节点
                n1 = n2->next;       // NULL
            }
        }
        else
        {
            n2 = n1; // 下一个节点
            n1 = n1->next;
        }
    }
    return adjacents;
}

// 4.3 相邻节点形成路径合集
PATHS FromPathsFromNodes(NEIGHBOR adjacents, PATH path, PATHS paths) // 节点集合中的每个节点（不在路径中）挨个加入路径，依次形成路径集合
{
    PATH tempath;
    adjacents = DeleteNodeInPath(adjacents, path); // 删除构成回路的节点
    while (adjacents)                              // 所有不构成回路的节点
    {
        tempath = CopyPath(path);                                // 复制路径
        tempath = Add_A_Node_To_Path(&adjacents->node, tempath); // 在路径中加入一个节点
        paths = Add_A_Path_To_Paths(tempath, paths);             // 新路径加入路径集合
        adjacents = adjacents->next;                             // 下一个节点
    }
    return (paths); // 返回路径集合
}

// 4.4 判断当前节点在迷宫中是否合法
STATUS Judge(NODE node, int size)
{
    if (node.x < 0 || node.x >= size)
        return FALSE;
    if (node.y < 0 || node.y >= size)
        return FALSE;
    if (Maze[node.x][node.y] == 0)
        return FALSE;
    return TRUE;
}

// 4.5 变换节点的位置
void Exchange(NODE *node, int hori, int vert)
{
    node->x = node->x + hori;
    node->y = node->y + vert;
}

// 4.6 相邻节点集合的生成
NEIGHBOR ExpandNodes(NODE node, int size)
{
    NEIGHBOR adjacents = NULL;
    NODE tempnode;
    STATUS legal = FALSE;
    Set(&tempnode, &node);
    Exchange(&tempnode, -1, 0); // 向左移动
    legal = Judge(tempnode, SIZE);
    if (legal == TRUE)
        adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode, &node);
    Exchange(&tempnode, 1, 0); // 向右移动
    legal = Judge(tempnode, SIZE);
    if (legal == TRUE)
        adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode, &node);
    Exchange(&tempnode, 0, -1); // 向上移动
    legal = Judge(tempnode, SIZE);
    if (legal == TRUE)
        adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode, &node);
    Exchange(&tempnode, 0, 1); // 向下移动
    legal = Judge(tempnode, SIZE);
    if (legal == TRUE)
        adjacents = Add_A_Adjacents(adjacents, tempnode);

    return adjacents;
}

// 5.1 路径长度计算
long int EvaluateLength(PATH path)
{
    int count = 0;
    while (path != NULL)
    {
        path = path->next;
        count++;
    }
    return count;
}

// 5.2 未来评估函数
float Evaluate(NODE *node1, NODE *node2)
{
    double res = 0;
    // res=sqrt((node1->x-node2->x)*(node1->x-node2->x)+(node1->y-node2->y)*(node1->y-node2->y));  //欧式距离
    res = abs(node1->x - node2->x) + abs(node1->y - node2->y); // 曼哈顿距离
    return res;
}

// 5.3 历史评估函数
void EvaluateAdjacents(NEIGHBOR adjacents, NODE *node, NODE *end)
{
    NEIGHBOR br = adjacents;
    while (br)
    {
        br->node.evaluate = Evaluate(&(br->node), end);
        br->node.step = node->step + 1;
        br = br->next;
    }
}

// 6.1 复制个体函数
INDIVIDUAL CopyIndividual(INDIVIDUAL population) // 复制染色体所有信息并返回新染色体
{
    INDIVIDUAL tempPopulation;
    for (int i = 0; i < population.chromlength; i++) // 逐个复制染色体的二进制信息
    {
        tempPopulation.chrom[i] = population.chrom[i];
    }
    tempPopulation.chromlength = population.chromlength; // 复制染色体的实际长度
    tempPopulation.fitness = population.fitness;         // 复制染色体的适应度函数值
    return tempPopulation;                               // 返回新染色体
}

// 6.2 将染色体解码成搜索路径
PATH Decoding(NODE start, NODE end, INDIVIDUAL indi)
// 将染色体解码为路径 00表示向右  01表示向上  10表示向左  11表示向下
{
    NEIGHBOR adjacents = NULL;
    NODE tempnode;
    int i, j;
    int nowx = start.x;
    int nowy = start.y;
    for (i = 0, j = 1; j <= indi.chromlength; i = i + 2, j = j + 2)
    {
        if (indi.chrom[i] == 0 && indi.chrom[j] == 0)
        { // 向右
            tempnode.x = nowx;
            tempnode.y = nowy + 1;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if (indi.chrom[i] == 0 && indi.chrom[j] == 1)
        { // 向上
            tempnode.x = nowx - 1;
            tempnode.y = nowy;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if (indi.chrom[i] == 1 && indi.chrom[j] == 0)
        { // 向左
            tempnode.x = nowx;
            tempnode.y = nowy - 1;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if (indi.chrom[i] == 1 && indi.chrom[j] == 1)
        {
            tempnode.x = nowx + 1;
            tempnode.y = nowy; // 向下
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        nowx = tempnode.x;
        nowy = tempnode.y;
        if (nowx == end.x && nowy == end.y)
            break;
    }
    return adjacents;
}

// 6.3 染色体个体适应度求解函数
void EvaluateIndividual(INDIVIDUAL *indi, NODE start, NODE end)
{
    int nowDist, minDist = 32767;
    PATH tempath = NULL;
    tempath = Decoding(start, end, *indi); // 染色体个体解码为旅行商路径
    while (tempath)
    {
        nowDist = Evaluate(&tempath->node, &end);
        if (nowDist < minDist)
            minDist = nowDist;
        tempath = tempath->next;
    }
    indi->fitness = minDist; // 旅行商路径长度为染色体个体的适应度函数值
}

// 6.4 对旅行商路径进行染色体编码
void Coding(PATH path, INDIVIDUAL *indi, NODE start, NODE end)
// 对路径进行染色体编码 00表示向右  01表示向上  10表示向左  11表示向下
{
    int i = 0;
    EvaluateIndividual(indi, start, end);
    PATH now = path->next;
    while (now)
    {
        if (now->node.y == path->node.y + 1)
        {
            indi->chrom[i++] = 0;
            indi->chrom[i++] = 0;
        }
        else if (now->node.x == path->node.x - 1)
        {
            indi->chrom[i++] = 0;
            indi->chrom[i++] = 1;
        }
        else if (now->node.y == path->node.y - 1)
        {
            indi->chrom[i++] = 1;
            indi->chrom[i++] = 0;
        }
        else if (now->node.x == path->node.x + 1)
        {
            indi->chrom[i++] = 1;
            indi->chrom[i++] = 1;
        }
        path = path->next;
        now = now->next;
    }
    indi->chromlength = i;
}

// 6.5 在给定搜索起点后随机初始化一条长度为STEP的路径
PATH InitTraPath(NODE start, PATH path)
// 给定搜索起点形成随机路径
{
    NODE temp;
    temp.x = start.x;
    temp.y = start.y;
    int i, n;
    path = Add_A_Node_To_Path(&temp, path);
    for (i = 0; i < STEP; i++)
    {
        Delay();
        n = rand() % 4;
        if (n == 0)
        { // 向右
            temp.y = temp.y + 1;
            if (Judge(temp, SIZE))
                path = Add_A_Node_To_Path(&temp, path);
            else
            {
                i--;
                temp.y = temp.y - 1;
                continue;
            }
        }
        else if (n == 1)
        { // 向上
            temp.x = temp.x - 1;
            if (Judge(temp, SIZE))
                path = Add_A_Node_To_Path(&temp, path);
            else
            {
                i--;
                temp.x = temp.x + 1;
                continue;
            }
        }
        else if (n == 2)
        { // 向左
            temp.y = temp.y - 1;
            if (Judge(temp, SIZE))
                path = Add_A_Node_To_Path(&temp, path);
            else
            {
                i--;
                temp.y = temp.y + 1;
                continue;
            }
        }
        else if (n == 3)
        { // 向下
            temp.x = temp.x + 1;
            if (Judge(temp, SIZE))
                path = Add_A_Node_To_Path(&temp, path);
            else
            {
                i--;
                temp.x = temp.x - 1;
                continue;
            }
        }
    }
    return path;
}

// 6.6 在给定出发位置后初始化搜索路径的一条染色体
void InitIndividual(NODE start, NODE end, INDIVIDUAL *indi)
{
    PATH trapath = NULL;
    trapath = InitTraPath(start, trapath);
    RevPath(trapath);
    Coding(trapath, indi, start, end);
}

// 6.7 在给定出发位置和种群规模后随机初始化旅行商的种群路径
void InitPopulation(NODE start, NODE end, int popsize, INDIVIDUAL population[])
// 给定旅行商路径的种群数量，随机初始化种群
{
    int i = 0;
    srand((unsigned)time(NULL));  // 时间为随机数种子
    for (i = 0; i < popsize; i++) // 初始化个体
    {
        InitIndividual(start, end, &population[i]); // 随机初始化路径的染色体个数
    }
}

// 6.8 用来计算搜索路径种群每个个体的适度值函数值
void EvaluatePopulation(int popsize, INDIVIDUAL population[], NODE start, NODE end)
// 对种群每个个体适应度函数值的求解
{
    int i;
    for (i = 0; i < popsize; i++)
    {
        EvaluateIndividual(&population[i], start, end); // 对每条染色体个体适应度函数的求解
    }
}

// 6.9 染色体个体的有效性
STATUS Efficent(NODE start, NODE end, INDIVIDUAL indi) // 判断路径个体有效性
{
    STATUS flag = TRUE;
    PATH path;
    path = Decoding(start, end, indi);
    while (path)
    {
        if (Judge(path->node, SIZE) == FALSE)
        {
            flag = FALSE;
        }
        path = path->next;
    }
    return flag;
}

// 7.1 选择算子：从路径种群中采用轮盘赌选择法来选取新种群
void SelectOperator(int popsize, INDIVIDUAL population[])
// 选择算子：从当前路径染色体种群population中采用轮盘赌选择法来选择个体进而形成新种群
{
    int i, j;
    double p, sum;                                   // p存放随机概率，sum存放个体适应率和累计适应率
    double *ps;                                      // 当代种群染色体个数的适应率
    INDIVIDUAL *newpopulation;                       // 新种群
    ps = (double *)malloc(popsize * sizeof(double)); // 开辟新路径染色体种群对应的概率空间
    newpopulation = (INDIVIDUAL *)malloc(popsize * sizeof(INDIVIDUAL));
    for (sum = 0, i = 0; i < popsize; i++)
    {
        sum += population[i].fitness; // sum存放种群适应值总和
    }
    for (i = 0; i < popsize; i++)
    {
        ps[i] = population[i].fitness / sum; // 路径染色体个体的概率
    }
    for (sum = 0, i = 0; i < popsize; i++)
        sum += 1 - ps[i]; // 路径染色体个体的概率之和
    for (i = 0; i < popsize; i++)
        ps[i] = (1 - ps[i]) / sum; // 路径染色体个体概率非新概率
    for (i = 1; i < popsize; i++)
        ps[i] += ps[i - 1];       // 新概率构成轮盘
    for (i = 0; i < popsize; i++) // for循环采用轮盘赌选择法，选择popsize个个体
    {
        Delay();
        p = rand() % 1000 / 1000.0; // 得到千分位小数的随机数
        for (j = 0; ps[j] < p; j++)
            ;                             // 转动轮盘
        newpopulation[i] = population[j]; // 选出一个数暂存于newpopulation中
    }
    for (i = 0; i < popsize; i++)
    {
        population[i] = newpopulation[i]; // 更新种群population
    }
    free(ps); // 回收数据单元
    free(newpopulation);
}

// 7.2 交叉算子
void CrossoverOperator(int popsize, INDIVIDUAL population[], double pc, NODE start, NODE end)
{
    int i, j, *index = NULL, point, temp, count;
    double p;
    index = (int *)malloc(popsize * sizeof(int)); // 形成一维数组
    for (i = 0; i < popsize; i++)
        index[i] = i;             // 初始化数组index[],种群索引
    for (i = 0; i < popsize; i++) // 打乱种群顺序
    {
        point = rand() % (popsize - 1);
        temp = index[i];
        index[i] = index[point + 1];
        index[point + 1] = temp;
    }
    i = 0;
    while (i < popsize - 1)
    {
        count = 0;
        p = rand() % 1000 / 1000.0;
        if (p < pc) // 根据概率选取第i条染色体
        {
        LOOP:
            point = rand() % (population[i].chromlength - 1) + 1;
            for (j = point; j < population[i].chromlength; j++)
            {
                temp = population[index[i]].chrom[j]; // 从交叉点逐位进行交换
                population[index[i]].chrom[j] = population[index[i + 1]].chrom[j];
                population[index[i + 1]].chrom[j] = temp;
            }
            if (!Efficent(start, end, population[index[i]]) || !Efficent(start, end, population[i + 1]))
            {
                for (j = point; j < population[i].chromlength; j++)
                {
                    // 恢复原有个体
                    temp = population[index[i]].chrom[j]; // 从交叉点逐位进行交换
                    population[index[i]].chrom[j] = population[index[i + 1]].chrom[j];
                    population[index[i + 1]].chrom[j] = temp;
                }
                count++;
                Delay();
                if (count > MAXTRY)
                {
                    i += 2;
                    continue;
                }
                goto LOOP;
            }
            i += 2; // 索引相邻两个体
        }
    }
}

// 7.3 变异算子
void MutateOperator(int popsize, INDIVIDUAL population[], double pm, NODE start, NODE end)
{
    int i, j, count;
    double p;
    INDIVIDUAL indi; // 染色体个体
    i = 0;
    while (i < popsize)
    {
        count = 0;
    LOOP:
        indi = CopyIndividual(population[i]);
        for (j = 2; j < population[i].chromlength - 1; j++)
        {
            p = rand() % 1000 / 1000.0; // 随机概率
            if (p < pm)
                indi.chrom[j] = (indi.chrom[j] == 0) ? 1 : 0; // 根据编译概率进行0和1变换
        }
        if (Efficent(start, end, indi) == FALSE)
        {
            Delay();
            if (count > MAXTRY)
            {
                i++;
                continue;
            }
            goto LOOP; // 变异后旅行商路径无效
        }
        population[i] = indi;
        i++; // 下一条染色体个体
    }
}

// 7.4 在路径种群中通过遗传算子产生新种群
void GenerateNextPopulation(int popsize, INDIVIDUAL population[], double pc, double pm, NODE start, NODE end)
// 通过遗传算子生成下一代群体
{
    SelectOperator(popsize, population);                    // 选择生成群体population
    CrossoverOperator(popsize, population, pc, start, end); // 交换生成群体population
    MutateOperator(popsize, population, pm, start, end);    // 变异生成群体population
}

// 7.5 从路径种群中选取最优(路径最短)的路径染色体，更新迄今为止最优的路径染色体
void GetBestIndividual(int popsize, INDIVIDUAL population[], INDIVIDUAL *bestindividual, INDIVIDUAL *currentbestindividual)
//*bestindividual为当前种群中最优个体，*currentbestindividual为程序运行不断进化迄今为止最优个体
// 从路径染色体种群population[]中求最优个体
{
    int i;
    *bestindividual = population[0]; // 默认种群中第0个个体为最优个体
    for (i = 1; i < popsize; i++)    // 种群中的其他个体
    {
        if (population[i].fitness <= bestindividual->fitness) // 依次比较，找出最优个体
        {
            *bestindividual = population[i]; // 更新种群中的最优个体
        }
    }
    if (bestindividual->fitness < currentbestindividual->fitness)
    // 当前代最优个体bestindividual与迄今为止最优个体currentbestindividual进行比较
    {
        *currentbestindividual = *bestindividual; // 更新迄今为止最优个体
    }
}

// 8.1 遗传进化
void GA(NODE start, NODE end, int popsize, double pc, double pm, int generation, INDIVIDUAL *currentbestindividual)
// 遗传进化过程
{
    INDIVIDUAL *population, bestindividual, oldbestindividual; // 种群、最优个体                                                                 //明文路径
    int i;
    population = (INDIVIDUAL *)malloc(popsize * sizeof(INDIVIDUAL)); // 分配种群单元
    InitPopulation(start, end, popsize, population);                 // 初始化种群
    bestindividual = population[0];                                  // 默认初始种群中的最优个体
    for (i = 1; i < popsize; i++)
    {
        if (population[i].fitness < bestindividual.fitness) // 依次比较找出最优个体
        {
            bestindividual = population[i]; // 更新初始种群中最优个体
        }
    }
    *currentbestindividual = bestindividual; // 初始种群中的最优个体为进化过程迄今为止最优个体
    oldbestindividual = bestindividual;      // 迄今为止最优个体为过往最优个体
    i = 0;
    while (i < generation) // 连续进化generation代，最优个体不变
    {
        GenerateNextPopulation(popsize, population, pc, pm, start, end);                // 产生新一代种群【选择、交叉、变异】
        EvaluatePopulation(popsize, population, start, end);                            // 评估新一代种群
        GetBestIndividual(popsize, population, &bestindividual, currentbestindividual); // 获取种群中最优个体和迄今为止最优个体
        if (fabs(currentbestindividual->fitness - oldbestindividual.fitness) < 1e-5)
            i++; // 连续进化的代数统计
        else
        {
            oldbestindividual = *currentbestindividual; // 更新过往最优个体
            i = 0;                                      // 连续进化的代数计数归零
        }
    }
}

// 8.2 全局遗传路径搜索[GA]
int SearchPath_GA(NODE start, NODE end)
{
    int minstep = 32767, nowstep;
    STATUS flag, allflag = FALSE;
    PATH path = NULL;
    INDIVIDUAL currentbestindividual; // 当前最优个体
    double pc = 0.6;                  // 交叉率为0.25-0.99
    double pm = 0.1;                  // 变异率为0.001-0.01
    int popsize = 10;                 // 种群数
    int generation = 500;             // 连续进化最优个体，代数不变
    int count = 30;                   // 求解次数
    for (int i = 0; i < count; i++)   // 求解count次
    {
        GA(start, end, popsize, pc, pm, generation, &currentbestindividual); // 智能算法——遗传算法求解
        path = Decoding(start, end, currentbestindividual);                  // 解码为路径
        path = Add_A_Node_To_Path(&start, path);                             // 所有路径加上起点
        flag = IsInPath(end, path);                                          // 判断终点是否在路径中
        if (flag == TRUE)
            allflag = TRUE;
        nowstep = EvaluateLength(path);
        if (nowstep < minstep)
            minstep = nowstep;
        printf("Now is %d Times Try , Resule Path:", i);
        PriPath(path);
        printf("Step=%d,Status=%d\n", nowstep, flag);
        PriMaze(path, start, end);
        printf("=========================\n");
        if (nowstep == MINISTEP)
            break;
    }
    if (allflag == FALSE)
        minstep = 0;
    return minstep;
}

// 8.3 盲目路径搜索[DFS]
STATUS SearchPath_DFS(NODE *start, NODE *end, PATH *path) // 判断终点是否在迷宫中，并获取路径
{
    NODE node;
    NEIGHBOR adjacents;
    STACK stack = NULL;
    STATUS flag = FALSE;
    PATH tempath = NULL;
    PATHS paths = NULL;
    tempath = Add_A_Node_To_Path(start, tempath); // 初始节点形成路径
    stack = Push_A_Path(stack, tempath);          // 路径进栈
    while (stack)                                 // 任意一条路径
    {
        tempath = ClearPath(tempath);               // 清空路径
        stack = Pop_A_Node(stack, &node, &tempath); // 出栈
        if (equal(&node, end) != 0)                 // 目标节点
        {
            flag = TRUE;               // 找到目标节点
            *path = CopyPath(tempath); // 获取路径
            break;
        }
        adjacents = ExpandNodes(node, SIZE);                   // 相邻的所有节点
        paths = FromPathsFromNodes(adjacents, tempath, paths); // 形成不带回路的路径集合
        stack = PushPaths(stack, paths);                       // 所有路径进栈
        paths = ClearPaths(paths);                             // 回收所有路径
    }
    ClearStack(stack); // 清空堆栈
    return (flag);
}

// 8.4 启发式路径搜索[A*]
STATUS SearchPath_A(NODE *start, NODE *end, PATH *path) // 判断节点是否在图中，并获取路径
{
    NODE node;
    NEIGHBOR adjacents;
    STACK stack = NULL;
    STATUS flag = FALSE;
    PATH tempath = NULL;
    PATHS paths = NULL;
    start->step = 0;
    start->evaluate = Evaluate(start, end);
    tempath = Add_A_Node_To_Path(start, tempath); // 初始节点形成路径
    stack = Push_A_Path(stack, tempath);          // 路径进栈
    while (stack)                                 // 任意一条路径
    {
        tempath = ClearPath(tempath);                                 // 清空路径
        stack = Pop_A_Node_Heuristic_by_Mini(stack, &node, &tempath); // 出栈
        if (equal(&node, end) != 0)                                   // 目标节点
        {
            flag = TRUE;               // 找到目标节点
            *path = CopyPath(tempath); // 获取路径
            break;
        }
        adjacents = ExpandNodes(node, SIZE); // 相邻的所有节点
        EvaluateAdjacents(adjacents, &node, end);
        paths = FromPathsFromNodes(adjacents, tempath, paths); // 形成不带回路的路径集合
        stack = PushPaths(stack, paths);                       // 所有路径进栈
        paths = ClearPaths(paths);                             // 回收所有路径
    }
    ClearStack(stack); // 清空堆栈
    return (flag);
}

int main()
{
    int step, length;
    PATH path = NULL;
    STATUS flag;
    NODE start = {1, 0, 0.0, 0.0}, end = {6, 7, 0.0, 0.0};
    printf("[INFO]");
    printf("Search from");
    PriNode(start);
    printf("to");
    PriNode(end);
    printf("\n");
    int mode;
    printf("[MENU]请选择模式:【0】退出 【1】遗传算法求解 【2】盲目搜索求解 【3】启发式求解\n");
    printf("[INPUT]请输入选择:");
    while (scanf("%d", &mode))
    {
        if (mode == 0)
        {
            exit(0);
        }
        else if (mode == 1)
        {
            step = SearchPath_GA(start, end);
            if (step == 0)
                printf("[INFO]Using GA Algorithm , Status= 0 \n");
            else
                printf("[INFO]Using GA Algorithm , Status = 1 ,Step = %d\n", step);
            printf("=========================\n");
        }
        else if (mode == 2)
        {
            flag = SearchPath_DFS(&start, &end, &path);
            length = EvaluateLength(path);
            printf("Path:");
            RevPath(path);
            PriPath(path);
            printf("[INFO]Using DFS Algorithm , Status = %d ,Step = %d\n", flag, length);
            PriMaze(path, start, end);
            printf("=========================\n");
        }
        else if (mode == 3)
        {
            flag = SearchPath_A(&start, &end, &path);
            length = EvaluateLength(path);
            printf("Path:");
            RevPath(path);
            PriPath(path);
            printf("[INFO]Using A* Algorithm , Status = %d ,Step = %d\n", flag, length);
            PriMaze(path, start, end);
            printf("=========================\n");
        }
        printf("[MENU]请选择模式:【0】退出 【1】遗传算法求解 【2】盲目搜索求解 【3】启发式求解\n");
        printf("[INPUT]请输入选择:");
    }

    ClearPath(path);
    return 0;
}